package com.cuz.前缀和;

public class NumMatrix {

    int [][]sumArray;
    public NumMatrix(int[][] matrix) {
        this.sumArray = new int[matrix.length][matrix[0].length];

        int rows = matrix.length;
        int cols = matrix[0].length;

        for(int r = 0; r<rows ; r++){
            for(int c = 0; c<cols ; c++){
              sumArray[r][c] =  outBoundGet(sumArray,r,c-1)
              + outBoundGet(sumArray,r-1,c)
              +outBoundGet(matrix,r,c)-outBoundGet(sumArray,r-1,c-1);
            }
        }
    }

    private int outBoundGet(int[][]arr,int r,int c){
        try{
            return arr[r][c];
        }catch(Exception e){
            return 0;
        }
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {

        int r2c2 = outBoundGet(sumArray,row2,col2);

        int r1c1 = outBoundGet(sumArray,row1-1,col1-1);

        int r1c2 = outBoundGet(sumArray,row1-1,col2);
        int r2c1 = outBoundGet(sumArray,row2,col1-1);

        return r2c2 - r1c2 - r2c1 + r1c1;
    }

    public static void main(String[] args) {

        int[][] nums = {{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},
                {4,1,0,1,7},{1,0,3,0,5}};
        NumMatrix numMatrix = new NumMatrix(nums);
        System.out.println(numMatrix.sumRegion(1, 1, 2, 2));
    }
}
